iT邦幫忙

2021 iThome 鐵人賽

DAY 16
0
Software Development

30天用JavaScript刷題刷起來!系列 第 16

Day 16 : Remove Nth Node From End of List

  • 分享至 

  • xImage
  •  

今天直接來看題目的敘述:Given the head of a linked list, remove the nth node from the end of the list and return its head.

也就是我們要從linked list尾端數第n個node並把它移除後,再將它回傳。

我們應該如何下手?

今天題目給的事單向連結串列(single linked list),而非雙向鏈接串列如下圖 (Doubly linked list),雙向鏈接和單向連結的差異主要是雙向可以知道前面和後面的node,所以如果題目給的是雙向鏈結,解題就會相對容易。
https://ithelp.ithome.com.tw/upload/images/20211001/20141729bVoCvPoBUO.png

那我們現在既然不能直接從後面開始倒過來拜訪node,這裡就要使用我們在解linked list時常用到的技巧 → pointer 兩個指標來追蹤

利用範例Input: head = [1,2,3,4,5], n = 2來說明

1 → 2 → 3 → 4 → 5 → null

我們宣告一個First (F)和Second (S)指標來追蹤

一開始我們把F和S指標都放在1身上

然後讓S走兩步( n = 2)來到 3 變成

1 → 2 → 3 → 4 → 5 → null
^       ^
F       S

然後們讓F和S一起往右移動直到S摸到null為止

來看下面不會動的動畫,看會怎麼樣

			    1 → 2 → 3 → 4 → 5 → null
step1			^       ^
			    F       S
step2                ^       ^
			         F       S
step3                   ^       ^
			            F       S
step4                        ^        ^
			                 F        S

偷看一下leetCode的解答
Output: [1,2,3,5]

有沒有發現現在的F剛好就在我們要移除的4身上!!
然後我們就可以把3的next換成5其實這題就解決了!

不過,我們應該還要還要考慮到

  1. 我們根本不知道4的前面是3
    那我們應該怎麼做?
    我們在還可以知道4的前面是3的時候應該是second指標將要移到null的時候,也就是在共同前進的while判斷應該要停止在second.next === null 之前

  2. 萬一今天n換成5,一開始走了5步後會變成如下,也就是我們就把頭砍掉即可

    			    1 → 2 → 3 → 4 → 5 → null
    step1			^                    ^
    			    F                    S
    
  3. 不要忘記有下面這種情況,

Input: head = [1], n = 1
Output: []

時間複雜度為:O(n),空間複雜度:O(1)

來看最後的實作

var removeNthFromEnd = function (head, n) {
  let step = 1;
  let first = head;
  let second = head;
  // step用來確保我們先移動second的步數
  while (step <= n) {
    second = second.next;
    step++;
  }
  // 考慮情況二
  if (second === null) {
    if (head.next) {
      head.val = head.next.val;
      head.next = head.next.next;
    } else {
		// 考慮情況三
      head = null
    }
    // 做完就沒事了
    return head;
  }
  // 考慮情況一
  while (second.next !== null) {
    second = second.next;
    first = first.next;
  }
  // second.next === null 時直接把first.next換掉
  first.next = first.next.next;
  return head;
};

明日題目預告:再玩一題Linked Lists相關題吧!
Add Two Numbers


上一篇
Day 15:Remove Duplicates from linked list
下一篇
Day 17 : Add Two Numbers
系列文
30天用JavaScript刷題刷起來!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言